#!/usr/bin/env python

'''
a simple script to use a brute-force search method to find a
solution to the famous "Chiffres" puzzle from the TV show
named "Des Chiffres et des lettres"
(known as "Countdown" in the UK, and as "Cijfers en Letters"
in Dutch).
See: http://fr.wikipedia.org/wiki/Des_chiffres_et_des_lettres

Written by: Jos de Kloe, 5-Sep-2013
License: GPL v3
'''

from numpy.random import random_integers, seed
from fractions import Fraction

ALLOWED_OPERATORS = ['-','+','/','*']

class operator:
    def __init__(self,txt_op):
        self.txt_op = txt_op
        # assume commutative, i.e.: a+b = b+a
        self.is_commutative = True
        if txt_op in ['-','/']:
            self.is_commutative = False
        # assume associative, i.e.: (x*y)*z = x*(y*z) 
        self.is_associative = True
        if txt_op in ['-','/']:
            self.is_associative = False
    def __call__(self,x,y):
        if self.txt_op == '+':
            return x+y
        if self.txt_op == '-':
            return x-y
        if self.txt_op == '*':
            return x*y
        if self.txt_op == '/':
            if y==0:
                return None
            # use the Fraction module to test whether 
            # x is a proper multiple of y
            testresult = Fraction(x,y)
            if testresult.denominator==1:
                return x/y
            else:
                return None
        print 'Unknown operator: ',self.txt_op
        raise NotImplementedError
    def to_str(self,x,y):
        return '('+str(x)+self.txt_op+str(y)+')'
    
OPS = [operator(txt_op) for txt_op in ALLOWED_OPERATORS]

def calc_result(numbers):
    # case for starting with one number
    for i,nr in enumerate(numbers):
        remaining_numbers = numbers[:i]+numbers[i+1:]
        # print 'number = ',nr
        # print 'remaining_numbers = ',remaining_numbers
        if len(remaining_numbers)==1:
            for op in OPS:
                result = op(nr,remaining_numbers[0])
                result_txt = op.to_str(nr,remaining_numbers[0])
                if result is not None:
                    yield result, result_txt
                if not op.is_commutative:
                    # try reverse operation as well
                    result = op(remaining_numbers[0],nr)
                    result_txt = op.to_str(remaining_numbers[0],nr)
                    if result is not None:
                        yield result, result_txt
        else:
            for remaining_result, remaining_result_txt \
                    in calc_result(remaining_numbers):
                # print remaining_result
                if remaining_result is None:
                    continue
                for op in OPS:
                    result = op(nr,remaining_result)
                    result_txt = op.to_str(nr,remaining_result_txt)
                    if result is not None:
                        yield result, result_txt
                    if not op.is_commutative:
                        # try reverse operation as well
                        result = op(remaining_result,nr)
                        result_txt = op.to_str(remaining_result_txt,nr)
                        if result is not None:
                            yield result, result_txt

        # case for starting with a pair of numbers
        if len(remaining_numbers)>3:
            for j,nr2 in enumerate(remaining_numbers):
                remaining_numbers2 = remaining_numbers[:j]+\
                                     remaining_numbers[j+1:]
                for result1,result1_txt in calc_result([nr,nr2]):
                    for result2,result2_txt in calc_result(remaining_numbers2):
                        for op in OPS:
                            result = op(result1,result2)
                            result_txt = op.to_str(result1_txt,result2_txt)
                            if result is not None:
                                yield result, result_txt
                            if not op.is_commutative:
                                # try reverse operation as well
                                result = op(result2,result1)
                                result_txt = op.to_str(result2_txt,result1_txt)
                                if result is not None:
                                    yield result, result_txt
                # case for starting with a triple of numbers
                for k,nr3 in enumerate(remaining_numbers2):
                    remaining_numbers3 = remaining_numbers2[:k]+\
                                         remaining_numbers2[k+1:]
                    for result1,result1_txt in calc_result([nr,nr2,nr3]):
                        for result2,result2_txt in calc_result(remaining_numbers3):
                            for op in OPS:
                                result = op(result1,result2)
                                result_txt = op.to_str(result1_txt,result2_txt)
                                if result is not None:
                                    yield result, result_txt
                                if not op.is_commutative:
                                    # try reverse operation as well
                                    result = op(result2,result1)
                                    result_txt = op.to_str(result2_txt,result1_txt)
                                    if result is not None:
                                        yield result, result_txt
    # done
    
def solve_chiffres(target_number, source_numbers):
    print 'Problem to be solved:'
    print 'target_number     = ', target_number
    print 'source_numbers    = ', source_numbers
    print 'ALLOWED_OPERATORS = ', ALLOWED_OPERATORS

    smallest_diff = 1000
    nr_of_tries = 0
    for result, result_txt in calc_result(source_numbers):
        nr_of_tries += 1
        diff = abs(target_number-result)
        if diff < smallest_diff:
            print 'new closest result found after {} tries:'.format(nr_of_tries)
            print 'target_number: ',target_number,'result = ',result,\
                  ' method: ',result_txt
            smallest_diff = diff
            if diff==0:
                break
    if smallest_diff!=0:
        print 'no exact solution found after {} tries!'.format(nr_of_tries)
        print 'best result is:',result
        return (False, nr_of_tries, result_txt)
    else:
        print 'Exact result found in {} tries !'.format(nr_of_tries)
        return (True, nr_of_tries, result_txt)
        
if __name__=='__main__':
    # define nr of tests to run
    num_test_cases = 10
    # ensure the results are reproducible
    seed(123654)
    # counter for results
    num_solved_tests = 0
    results = []
    for i in range(num_test_cases):
        # target_number  = random_integers(low=0,high=1000,size=1)
        target_number  = random_integers(low=100,high=999,size=1)
        # source_numbers = random_integers(low=0,high=1000,size=6)
        source_numbers_raw = list(random_integers(low=1,high=14,size=6))
        # (1 a 10, 25, 50, 75 et 100)
        source_numbers = source_numbers_raw
        for i, sn in enumerate(source_numbers_raw):
            if sn==11:
                source_numbers[i] = 25
            if sn==12:
                source_numbers[i] = 50
            if sn==13:
                source_numbers[i] = 75
            if sn==14:
                source_numbers[i] = 100
        (solved, nr_of_tries, result_txt) = \
                 solve_chiffres(target_number, source_numbers)
        results.append((target_number,source_numbers,
                        solved, nr_of_tries, result_txt))
        if solved:
            num_solved_tests += 1

    print '='*50
    print 'Solved {} test cases out of {}.'.\
          format(num_solved_tests,num_test_cases)
    print '='*50
    for (target_number,source_numbers,
         solved, nr_of_tries, result_txt) in results:
        if solved:
            print 'exact   result after {:12d} tries: {} = {}'.\
                  format(nr_of_tries, target_number,result_txt)
        else:
            print 'closest result after {:12d} tries: {} = {}'.\
                  format(nr_of_tries, target_number,result_txt)
    print '='*50
        


